package leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.*;

public class LeetCodeMain61 {
    public int countSubstrings(String s) {
        int length=s.length();
        boolean[][] dp=new boolean[length][length];
        int count=0;
        for (int i = length-1; i>=0; i--) {
            for (int j = i; j < length; j++) {
                if (s.charAt(i)==s.charAt(j)){
                    if (j-i<=1){
                        count++;
                        dp[i][j]=true;
                    }
                    else if (dp[i+1][j-1]){
                        count++;
                        dp[i][j]=true;
                    }
                }
            }
        }
        return count;
    }
    public int countSubstrings1(String s) {
        if (s==null||s.length()==0){
            return 0;
        }
        int length=s.length();
        int[] dp=new int[length];
        int count=0;
        for (int i = 0; i < length; i++) {
            for (int j = i; j < length; j++) {
                if (isN(s,i,j)){
                    count++;
                }
            }
        }
        return count;
    }
    public boolean isN(String s,int start, int end){
        while (start<=end){
            if (s.charAt(start)!=s.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    public int numDistinct(String s, String t) {
        int length1=s.length();
        int length2=t.length();
        int[][] dp=new int[length1+1][length2+1];
        for (int i = 0; i <= length1; i++) {
            dp[i][0]=1;
        }
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                }else {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[length1][length2];
    }
    public int min(String word1,String word2){
        int length1=word1.length();
        int length2=word2.length();
        int[][] dp=new int[length1+1][length2+1];
        for (int i = 1; i <= length1; i++) {
            dp[i][0]=i;
        }
        for (int i = 1; i <= length2; i++) {
            dp[0][i]=i;
        }
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }
        }
        return dp[length1][length2];
    }
//    public int minDistance(String word1, String word2) {
//        int length1=word1.length();
//        int length2=word2.length();
//        int[][] dp=new int[length1+1][length2+1];
//        for (int i = 1; i <= length1; i++) {
//            dp[i][0]=i;
//        }
//        for (int i = 1; i <= length2; i++) {
//            dp[0][i]=i;
//        }
//        for (int i = 1; i <= length1; i++) {
//            for (int j = 1; j <= length2; j++) {
//                if (word1.charAt(i-1)==word2.charAt(j-1)){
//                    dp[i][j]=dp[i-1][j-1];
//                }else {
//                    dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+1;
//                }
//            }
//        }
//        return dp[length1][length2];
//    }
    public boolean isSubsequence(String s, String t) {
        int length1=s.length();
        int length2=t.length();
        int[][] dp=new int[length1+1][length2+1];
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (s.charAt(i-1)==t.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else {
                    dp[i][j]=dp[i][j-1];
                }
            }
        }
        if (dp[length1][length2]!=s.length()){
            return false;
        }
        return true;
    }
    public int getValue(int[] gifts, int n) {
        // write code here
        HashMap<Integer,Integer> map=new HashMap<>();
        int max1=0;
        int max2=0;
        int count=0;
        int length=gifts.length;
        for (int i = 0; i < length; i++) {
            map.put(gifts[i],map.getOrDefault(gifts[i],0)+1);
        }
        for (Map.Entry<Integer,Integer> num:map.entrySet()) {
            if (num.getValue()>max1){
                count=num.getKey();
                max2=max1;
                max1=num.getValue();
            }
        }
        if (max1*2<length){
            return 0;
        }
        return count;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()){
            String str1=in.nextLine();
            String str2=in.nextLine();
            int length1=str1.length();
            int length2=str2.length();
            int[][] dp=new int[length1+1][length2+1];
            dp[0][0]=0;
            for (int i = 1; i <= length1; i++) {
                dp[i][0]=i;
            }
            for (int i = 1; i <= length2; i++) {
                dp[0][i]=i;
            }
            for (int i = 1; i <= length1; i++) {
                for (int j = 1; j <= length2; j++) {
                    if(str1.charAt(i-1)==str2.charAt(j-1)){
                        dp[i][j]=dp[i-1][j-1];
                    }else {
                        dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i][j-1],dp[i-1][j]))+1;
                    }
                }
            }

            System.out.println(dp[length1][length2]);
        }

    }
}
